package main

import (
	"fmt"
	"sort"
)

/**
执行用时：32 ms, 在所有 Go 提交中击败了70.70%的用户
内存消耗：8.1 MB, 在所有 Go 提交中击败了10.56%的用户
 */
func threeSum(nums []int) [][]int {

	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})

	res := [][]int{}
	for i := 0; i < len(nums); i++ {
		if nums[i] > 0 { break }
		if i > 0 && nums[i] == nums[i - 1] { continue }
		for j, k := i + 1, len(nums) - 1; j < k; j++ {
			if j > i + 1 && nums[j] == nums[j - 1] { continue }
			for j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0 { k-- }
			if nums[i] + nums[j] + nums[k] == 0 {
				res = append(res, []int{nums[i], nums[j], nums[k]})
			}
		}
	}
	return res
}

func main() {

	nums := []int{-1, 0, 1, 2, -1, -4}
	fmt.Println(threeSum(nums))
}
